/*
 * Node.cpp
 */

#include <iostream>
#include <algorithm> //for binary searching (lower_bound), swap
#include "Node.h"

using namespace std;

Node::Node(NodeType type) {
	if(type == LEAF_NODE)
		_numKeys = -1;
	else
		_numKeys = 0;

	_keys[0] = INT_MAX;
}

Node::~Node() {
}

//helper function to return node width
int Node::GetD() { return D_BREADTH; }

//Return type of node (Leaf or Index node)
NodeType Node::GetNodeType() {
	if(_numKeys >= 0)
		return INDEX_NODE;
	else
		return LEAF_NODE;
}

//Fetch number of keys currently in node
int Node::NumberOfKeys() {
	if(_numKeys < 0)
		return -1*_numKeys - 1;
	else
		return _numKeys;
}

//Set number of keys in node
void Node::SetNumberOfKeys(int num) {
	if(_numKeys < 0)
		_numKeys = -1*num - 1;
	else
		_numKeys = num;
}

//Increment internal key count tracker
int Node::IncrementNumberOfKeys() {
	if(_numKeys < 0) {
		--_numKeys;
		return NumberOfKeys();
	}
	else
		return ++_numKeys;
}

//Determines if node needs to split (is full)
bool Node::NeedsSplit() {
	return (NumberOfKeys() >= D_BREADTH);
}

//Determines if node is in need of rebalancing (unused since no deletion)
bool Node::NeedsMerge() {
	return (NumberOfKeys() <= D_BREADTH / 2);
}

//Insert key into key array in order, shifting greater keys back in the array
//Returns -1 if attempt to insert key in full index or key already exists
int Node::InsertKey(int key) {
	int insertIdx = -1;

	if(NumberOfKeys() <= D_BREADTH) { //verify node isn't "super" full, meaning d+1
		////Method good except for possibility of trying to insert an existing key
//		for(int idx = _numKeys - 1; _keys[idx] > key; idx--) {
//			_keys[idx+1] = _keys[idx];
//		}
//		int tmp = -1;
		for(int idx = 0; idx <= NumberOfKeys(); idx++) {
			if(_keys[idx] == key)
				break; //fail to insert key because key already exists
			else if(idx == NumberOfKeys()) { //copy final shifted key, or insert key at end
				if(insertIdx == -1)
					insertIdx = idx;
				swap(_keys[idx], key);
			}
			else if(_keys[idx] > key) { //copy in new key or shifted key
				if(insertIdx == -1)
					insertIdx = idx;
				swap(_keys[idx], key);
			}
		}
		if(insertIdx != -1)
			IncrementNumberOfKeys();
	}
	else
		cout << "Index attempted to insert key while full" << endl; //Index should never try to insert key into full node

	return insertIdx;
}

//Return index of first key for which (search key <= key) holds true
int Node::SearchKey(int key) {
//	int x = 0;
//	while(key > _keys[x] && x < NumberOfKeys()) {
//		x++;
//	}
//
//	return x;
	int *ptr = lower_bound(_keys, _keys+NumberOfKeys(), key);

	return (ptr - _keys);
}
